package com.algorithm;

import java.util.Hashtable;
import java.util.Map;

/**
 * <pre>
 *  狄克斯特拉算法（Dijkstra’s algorithm）
 *
 *  1、狄克斯特拉算法用于在加权图中查找最短路径；
 *  2、仅当权重为正时狄克斯特拉算法才管用；
 *  3、如果图中包含负权边，请使用 “贝尔曼-福德算法”
 * </pre>
 */
class DijkstraAlgorithm {


    public static void main(String[] args) {

        /*---------------------------- 初始化数据——图 ----------------------------*/
        Hashtable<String, Object> graph = new Hashtable<String, Object>();

        //  开始节点到各个节点的权重
        Hashtable<String, Integer> start = new Hashtable<String, Integer>();
        start.put("a", 6);
        start.put("b", 2);
        graph.put("start", start);

        //  a节点到fin节点的权重
        Hashtable<String, Integer> a = new Hashtable<String, Integer>();
        a.put("fin", 1);
        graph.put("a", a);

        //  b节点到fin节点的权重
        Hashtable<String, Integer> b = new Hashtable<String, Integer>();
        b.put("fin", 5);
        b.put("a", 3);
        graph.put("b", b);

        //  fin节点
        Hashtable<String, Integer> fin = new Hashtable<String, Integer>();
        graph.put("fin", fin);

        //  开销散列表
        Hashtable<String, Float> costs = new Hashtable<String, Float>();
        costs.put("a", 6f);
        costs.put("b", 2f);
        costs.put("fin", Float.POSITIVE_INFINITY);

        //  父节点散列表
        Hashtable<String, String> parents = new Hashtable<String, String>();
        parents.put("a", "start");
        parents.put("b", "start");

        //  处理过的散列表
        Hashtable<String, Boolean> processed = new Hashtable<String, Boolean>();


        /*---------------------------- 开始执行狄克斯特拉算法 ----------------------------*/
        //  在未处理的节点中找出开销最小的节点
        String node = findLowestCostNode(costs, processed);
        //  这个循环在所有节点都被处理过后结束
        while (node != null) {
            //  遍历当前节点的所有邻居
            Float cost = costs.get(node);
            Hashtable<String, Integer> neighbors = (Hashtable<String, Integer>) graph.get(node);
            for (Map.Entry<String, Integer> entry : neighbors.entrySet()) {
                float newCost = cost + entry.getValue();
                String key = entry.getKey();
                //  如果经过当前节点前往该邻居更近
                if (costs.get(key) > newCost) {
                    //  就更新该邻居的开销
                    costs.put(key, newCost);
                    //  同时将该邻居的父节点设置为当前节点
                    parents.put(key, node);
                }
            }

            //  将当前节点标记未处理过
            processed.put(node, true);
            //  找出接下来要处理的节点，并循环
            node = findLowestCostNode(costs, processed);
        }

        StringBuilder content = new StringBuilder();
        String step = "fin";
        content.insert(0, " =>> fin");
        while (!step.equals("start")) {
            step = parents.get(step);
            content.insert(0, " =>> " + step);
        }

        System.out.println("最短的路线为 " + content);
    }


    /**
     * 找出开销最低的节点
     *
     * @param costs     开销散列表
     * @param processed 处理过的散列表
     * @return 开销最低的节点名称
     */
    private static String findLowestCostNode(Hashtable<String, Float> costs, Hashtable<String, Boolean> processed) {
        //  最低成本
        float lowestCost = Float.POSITIVE_INFINITY;
        //  最低成本的节点名称
        String lowestCostNode = null;

        //  遍历所有节点
        for (Map.Entry<String, Float> entry : costs.entrySet()) {
            String node = entry.getKey();
            Float cost = entry.getValue();
            //  如果当前节点的开销更低并且未处理过
            if (cost < lowestCost && processed.get(node) == null) {
                //  就将其视为开销最低的节点
                lowestCost = cost;
                lowestCostNode = node;
            }
        }
        return lowestCostNode;
    }
}
